#include "HuffTree.hpp"
#include "Solution.hpp"
#include "Tournee.hpp"
#include <cassert>

HuffTree::HuffTree() EXC_THROWER()
{
	EXC_RETHROW_BEGIN()
	{
		std::deque<unsigned>		base(4);
		
		for (unsigned i = 0 ; i < 4 ; i++)
			base[i] = i;
			
		this->reset(base);
	}
	EXC_RETHROW_END()
}

// templatable
HuffTree::HuffTree(const std::deque<unsigned>& inBase) EXC_THROWER()
{
	EXC_RETHROW_BEGIN()
	{
		this->reset(inBase);
	}
	EXC_RETHROW_END()
}

void			HuffTree::reset(const std::deque<unsigned>& inBase)
{
	unsigned	k = (inBase.size() - 1);
	unsigned	shift = 0;
	unsigned	n_leaves = 0;
	unsigned	n_nodes = 0;
	unsigned 	i;
	unsigned	pred_n_leaves;
	
	if (inBase.size() == 1)
		EXC_THROW("vector given cannot have size 1");
	
	if (k == 0)
		EXC_THROW("vector given is empty");
		
	for (shift = 0 ; k != 0 ; shift++)
	{
		k >>= 1;
	}
	
	n_leaves = 1;
	n_leaves <<= shift;
	n_nodes = n_leaves + (n_leaves - 1);
	
	//std::cout << n_leaves << " " << n_nodes << std::endl;
	
	if (n_leaves > 0x80)
		EXC_THROW("unable to create n_leaves > 0x80");
    
    heNLeaves = n_leaves;
    heNNodes = n_nodes;
    
    for (int s = (shift) ; s > -1 ; s--)
    {		
		for (i = 0 ; i < n_leaves ; i++)
		{
			heWeight[(n_leaves - 1) + i] = 1 << (shift - s);
			if (s == (shift))
				heData[(n_leaves - 1) + i] = (i >= inBase.size()) ? i : inBase[i];
			else
				heData[(n_leaves - 1) + i] = 0x1000 | (((n_leaves << 1) - 1) + (i << 1));
				
			heLevel[(n_leaves - 1) + i] = s;
			
			if (s == 0)
				heFather[(n_leaves - 1) + i] = 0xFFFF;
			else
				heFather[(n_leaves - 1) + i] = ((n_leaves >> 1) - 1) + (i >> 1);
			
			if (s == shift)
				heIndexByLeaf[inBase[i]] = (n_leaves - 1) + i;
		}
		n_leaves >>= 1;
	}
	
	//heTournees.resize(heNNodes);
	//heEvals.resize(heNNodes);
	
	heMaxLevel = shift - 1;
}

HuffTree&		HuffTree::operator=(const HuffTree& inHuff)
{
	if (&inHuff == this)
		return (*this);
	
	heNNodes = inHuff.heNNodes;
	heNLeaves = inHuff.heNLeaves;
	memcpy(this->heWeight, inHuff.heWeight, 0xff * sizeof(unsigned int));
	memcpy(this->heData, inHuff.heData, 0xff * sizeof(unsigned short));
	memcpy(this->heLevel, inHuff.heLevel, 0xff * sizeof(unsigned short));
	memcpy(this->heFather, inHuff.heFather, 0xff * sizeof(unsigned short));
	heMaxLevel = inHuff.heMaxLevel;
	heSize = inHuff.heSize;
	heIndexByLeaf = inHuff.heIndexByLeaf;
	heIndexByLevel = inHuff.heIndexByLevel;
	
	return (*this);
}

HuffTree&       HuffTree::operator<<=(unsigned short inData) EXC_THROWER()
{
    unsigned    cur_index = 0;
    unsigned    switch_index = 0;
    
    if (inData > (heNLeaves - 1))
        EXC_THROW("invalid data, must be < heNLeaves");
        
    cur_index = heIndexByLeaf[inData];
    
    while (cur_index != 0)
    {
        switch_index = cur_index;
                    
        do
        {
            switch_index--;
        }   while (heWeight[switch_index] == heWeight[cur_index]);
        
        switch_index++;
        
        if (switch_index != cur_index)
            this->permut(cur_index, switch_index);
            
        heWeight[switch_index]++;
        cur_index = heFather[switch_index];
    }
    
    heWeight[cur_index]++;
    return (*this);
}


void        HuffTree::permut(unsigned short inIndex1,   unsigned short inIndex2)
{
    if (0 != (heData[inIndex1] & 0x1000))
    {
        // 1 : NODE, 2 : NODE
        if (0 != (heData[inIndex2] & 0x1000))
        {
            SWAP(heFather[((~0x1000) & heData[inIndex1]) + 0], heFather[((~0x1000) & heData[inIndex2]) + 0]);
            SWAP(heFather[((~0x1000) & heData[inIndex1]) + 1], heFather[((~0x1000) & heData[inIndex2]) + 1]);
        }
        // 1 : NODE, 2 : LEAF
        else
        {
            heFather[((~0x1000) & heData[inIndex1]) + 0] = inIndex2;
            heFather[((~0x1000) & heData[inIndex1]) + 1] = inIndex2;
            heIndexByLeaf[heData[inIndex2]] = inIndex1;
        }
    }
    else
    {
        // 1 : LEAF, 2 : NODE
        if (0 != (heData[inIndex2] & 0x1000))
        {
            heFather[((~0x1000) & heData[inIndex2]) + 0] = inIndex1;
            heFather[((~0x1000) & heData[inIndex2]) + 1] = inIndex1;
            heIndexByLeaf[heData[inIndex1]] = inIndex2;
        }
        // 1 : LEAF, 2 : LEAF
        else
        {
            SWAP(heIndexByLeaf[heData[inIndex1]], heIndexByLeaf[heData[inIndex2]]);
        }
    }
    
    // swap data
    SWAP(heData[inIndex1], heData[inIndex2]);
}

void        HuffTree::printDot(const std::string& inFilename) const EXC_THROWER()
{
    FILE*   fp = 0;
    
    if ((fp = fopen(inFilename.c_str(), "wt")) == 0)
    {
        std::cerr << ">> " << inFilename << std::endl;
        EXC_THROW("unable to open dot file");
    }
    
    fprintf(fp, "graph graphname {\n");
    
    for (unsigned i = 0 ; i < heNNodes ; i++)
    {
        if (0 != (heData[i] & 0x1000))
        {
            fprintf(fp, "%u [label=\"%.4x::%u::F:%.4x\"];\n", (unsigned int)heData[i], (unsigned int)heData[i], (unsigned int)heWeight[i], (i == 0) ? 0xFFFF : (unsigned int)heData[heFather[i]]);
            fprintf(fp, "%u -- %u;\n", (unsigned int)heData[i], (unsigned int)heData[((~0x1000) & heData[i])]);
            fprintf(fp, "%u -- %u;\n", (unsigned int)heData[i], (unsigned int)heData[((~0x1000) & heData[i]) + 1]);
        }
        else
        {
            fprintf(fp, "%u [label=\"%.4x::%u::F%.4x\"];\n", (unsigned int)heData[i], (unsigned int)heData[i], (unsigned int)heWeight[i], (unsigned int)heData[heFather[i]]);
            fprintf(fp, "%u [shape=box];\n", (unsigned int)heData[i]);
        }
    }
    
    fprintf(fp, "}\n\n");
    fclose(fp);
}

void        HuffTree::updateLevels()
{
    std::pair<unsigned, unsigned>   p;
    
    heLevel[0] = 0;
    heIndexByLevel.clear();
    
    for (unsigned i = 0 ; i < heNNodes ; i++)
    {
        if (0 != (heData[i] & 0x1000))
        {
            heLevel[((~0x1000) & heData[i])] = heLevel[i] + 1;
            heLevel[((~0x1000) & heData[i]) + 1] = heLevel[i] + 1;
        }
        
        p.first = heLevel[i];
        p.second = i;
        heIndexByLevel.insert(p);
    }
    
    heMaxLevel = heIndexByLevel.rbegin()->first;
}

void		HuffTree::execute()
{
	
}

void        HuffTree::buildSolutions(VRPTW& inVRPTW, SolutionEval* inEval) const
{
    std::multimap<unsigned, unsigned>::const_iterator    it;
    std::vector<Solution>	sols(heMaxLevel + 1, Solution(inVRPTW));
    unsigned                tournees_by_index[0xff];
    TourneeEvalResult       evalres;
    TourneeEvalResult       evalres2;
    std::vector<SolutionEval>	evalsols(heMaxLevel + 1);
    std::vector<unsigned>   sols_tournee(heMaxLevel + 1, 99);
    unsigned    			tournee;
    int						i;
    
    assert(inEval != 0);
    
    for (unsigned i = 0 ; i < (heMaxLevel + 1) ; i++)
    {
		sols[i].clear();
		sols_tournee[i] = 99;
	}
    memset(tournees_by_index, 128, 0xff * sizeof(unsigned));
    
    std::cout << "build solutions core" << std::endl;
    
    for (i = heMaxLevel ; i > -1 ; i--)
    {
        tournee = 0;
        
        for (it = heIndexByLevel.find(i) ; (it != heIndexByLevel.end()) && (it->first == (unsigned)i)  ; ++it)
        {
            //printf("exploring : %.4x (%.4x) : %u - %u\n", it->second, heData[it->second], it->first, i);
            
            if (0 == (0x1000 & heData[it->second]))
            {
                if ((heData[it->second] < 100))
                {
                    // std::cout << "it->second " << it->second << std::endl;
                    // std::cout << "data : " << heData[it->second] << std::endl;
                    sols[i][tournee].insertClient(Tournee::INSERT_END, heData[it->second]);
                    tournees_by_index[it->second] = tournee;
                    sols[i].validateTournee(tournee);
                    //std::cout << "eval" << std::endl;
                    sols[i][tournee].eval(&evalres);
                    sols[i].validateTournee(tournee);
                    tournee++;
                }
                else
                {
                    tournees_by_index[it->second] = 0xFFFFFFFF;
                }
            }
            else
            {
                if (tournees_by_index[((~0x1000) & heData[it->second])] == 0xFFFFFFFF)
                {
                    if (tournees_by_index[((~0x1000) & heData[it->second]) + 1] == 0xFFFFFFFF)
                    {
                        // left & right empty
                        tournees_by_index[it->second] = 0xFFFFFFFF;
                    }
                    else
                    {
                        // left empty
                        Tournee&          cur_tournee = sols[i][tournee];
                        const Tournee&    right_tournee = sols[(unsigned)(i + 1)][tournees_by_index[((~0x1000) & heData[it->second]) + 1]];
                        cur_tournee.append(right_tournee);
                        sols[i].validateTournee(tournee);
                        sols[i][tournee].eval(&evalres);
                        sols[i].validateTournee(tournee);
                        if (!evalres.erValable)
                        {
                            for (int j = (i - 1) ; j > -1 ; j--)
                            {
                                sols[j][sols_tournee[j]].append(right_tournee);
                                sols[j].validateTournee(sols_tournee[j]);
                                sols_tournee[j]--;
                            }
                            
                            tournees_by_index[it->second] = 0xFFFFFFFF;
                        }
                        else
                        {
                            tournees_by_index[it->second] = tournee;
                        }
                        tournee++;
                    }
                }
                else
                {
                    if (tournees_by_index[((~0x1000) & heData[it->second]) + 1] == 0xFFFFFFFF)
                    {
                        // right empty
                        Tournee&          cur_tournee = sols[i][tournee];
                        const Tournee&    left_tournee = sols[(unsigned)(i + 1)][tournees_by_index[((~0x1000) & heData[it->second])]];
                        cur_tournee.append(left_tournee);
                        sols[i].validateTournee(tournee);
                        sols[i][tournee].eval(&evalres);
                        sols[i].validateTournee(tournee);
                        if (!evalres.erValable)
                        {
                            for (int j = (i - 1) ; j > -1 ; j--)
                            {
                                sols[j][sols_tournee[j]].append(left_tournee);
                                sols[j].validateTournee(sols_tournee[j]);
                                sols_tournee[j]--;
                            }
                            
                            tournees_by_index[it->second] = 0xFFFFFFFF;
                        }
                        else
                        {
                            tournees_by_index[it->second] = tournee;
                        }
                        tournee++;
                    }
                    else
                    {
                        Solution                s1(inVRPTW);
                        Solution                s2(inVRPTW);
                        
                        s1.clear();
                        s2.clear();
                        
                        Tournee&                test_tournee = s1[0];
                        Tournee&                test_tournee2 = s2[0];
                        
                        // nothing empty
                        Tournee&          cur_tournee = sols[i][tournee];
                        const Tournee&    left_tournee = sols[(unsigned)(i + 1)][tournees_by_index[((~0x1000) & heData[it->second])]];
                        const Tournee&    right_tournee = sols[(unsigned)(i + 1)][tournees_by_index[((~0x1000) & heData[it->second]) + 1]];
                        
                        test_tournee.clear();
                        test_tournee.append(left_tournee);
                        s1.validateTournee(0);
                        test_tournee.append(right_tournee);
                        s1.validateTournee(0);
                        test_tournee.eval(&evalres);
                        s1.validateTournee(0);
                        
                        test_tournee2.clear();
                        test_tournee2.append(right_tournee);
                        s2.validateTournee(1);
                        test_tournee2.append(left_tournee);
                        s2.validateTournee(1);
                        test_tournee2.eval(&evalres2);
                        s2.validateTournee(1);
                        
                        if (evalres.erValable)
                        {
                            if (evalres2.erValable)
                            {
                                if (evalres2.erTotalTime < evalres.erTotalTime)
                                {
                                    cur_tournee.append(test_tournee2);
                                    sols[i].validateTournee(tournee);
                                    tournees_by_index[it->second] = tournee;
                                    tournee++;
                                }
                                else
                                {
                                    cur_tournee.append(test_tournee);
                                    sols[i].validateTournee(tournee);
                                    tournees_by_index[it->second] = tournee;
                                    tournee++;
                                }
                            }
                            else
                            {
                                cur_tournee.append(test_tournee);
                                sols[i].validateTournee(tournee);
                                tournees_by_index[it->second] = tournee;
                                tournee++;
                            }
                        }
                        else
                        {
                            if (evalres2.erValable)
                            {
                                cur_tournee.append(test_tournee2);
                                sols[i].validateTournee(tournee);
                                tournees_by_index[it->second] = tournee;
                                tournee++;
                            }
                            else
                            {
                                for (int j = (i - 1) ; j > -1 ; j--)
                                {
                                    sols[j][sols_tournee[j]].append(left_tournee);
                                    sols[j].validateTournee(sols_tournee[j]);
                                    sols_tournee[j]--;
                                    sols[j][sols_tournee[j]].append(right_tournee);
                                    sols[j].validateTournee(sols_tournee[j]);
                                    sols_tournee[j]--;
                                }
                                
                                tournees_by_index[it->second] = 0xFFFFFFFF; 
                            }
                        }
                        sols[i].validateTournee(tournee);
                        
                    }
                }
            }
        }
        
        /*if (!sols[i].isComplete())
            sols[i].complete();
        */
        //std::cout << sols[i].toString() << std::endl;
        sols[i].eval(&evalsols[i]);
        if ((i != heMaxLevel) && (evalsols[i] == evalsols[i + 1]))
			break;
        //std::cout << evalsol.toString() << std::endl;
        //break;
    }
    
    if (i == -1)
		i = 0;
    
    std::cout << sols[i].toString() << std::endl;
    *inEval = evalsols[i];
}

void        HuffTree::permutLeaves(unsigned short inLeaf1, unsigned short inLeaf2) EXC_THROWER()
{
	if (inLeaf1 == inLeaf2)
		return;
	
    this->permut(heIndexByLeaf[inLeaf1], heIndexByLeaf[inLeaf2]);
}

